/* 
    堆排序
*/
let arrSort = function (arr) {
    if (arr == null && arr.length < 2) return arr;
    return heapSort(arr, 0, arr.length - 1);
};
function heapSort(arr, low, high) {
    /* 堆排序 */
    let heapSize = 0;
    let resArr = [];
    arr.forEach((element, index, arr) => {
        while (arr[index] > arr[Math.floor((index - 1) / 2)] && index > 0) {
            let temp = arr[Math.floor((index - 1) / 2)];
            arr[Math.floor((index - 1) / 2)] = arr[index];
            arr[index] = temp;
            index = Math.floor((index - 1) / 2);
        }
        heapSize++;
    });
    console.log(arr);
    while (heapSize > 0) {
        resArr.unshift(arr[0]);
        heapify(arr, heapSize);
        heapSize--;
    }

    return resArr;
}

function heapify(arr, lastIndex) {
    /* 保持大顶堆化 */
    let flag = 0;
    arr[0] = arr[lastIndex - 1];
    arr.pop();
    while (arr[flag * 2 + 1]) {
        let large;
        if (arr[flag * 2 + 2]) {
            large = arr[flag * 2 + 1] > arr[flag * 2 + 2] ? flag * 2 + 1 : flag * 2 + 2;
        } else {
            large = flag * 2 + 1;
        }
        if (arr[large] > arr[flag]) {
            swap(arr, large, flag);
            flag = large;
        } else {
            break;
        }
    }
}

function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

let arr = [1, 6, 9, 6, 96, 56, 6, 56, 456, 6, 465455, 4, 5, 4, 100, 2, 45, 45, 23, 56, 89];
let resArr = arrSort(arr);
console.log(resArr);
